\documentclass{beamer}

\usepackage{beamerthemelined}
\usepackage{url}
\title{Byzantine Fault Tolerance (BFT)}
\author{Aditya Joshi}
\date{\today}

\begin{document}

\frame{\titlepage}
\section*{Outline}
\frame{\tableofcontents}

\section{Introduction}
\begin{frame}
    \frametitle{Need for BFT algorithms?}
\end{frame}

\section{System Model}
\begin{frame}
    \begin{itemize}
        \item Asynchronous System
        \item Independent node failures
        \item Cryptographic techniques
            \begin{itemize}
                \item Public/Private Keys
                \item Message Digests - D(m)
                \item Message Authentication Codes (MAC) - $\langle$m$\rangle$${_\sigma}_i$
            \end{itemize}
    \end{itemize}
\end{frame}

\section{Service Properties}
\begin{frame}
    \begin{itemize}
        \item Deterministic replicated service
        \item Safety: replicated service satisfies linearizability
        \item Liveness: clients eventually receive replies to requests
        \item Algorithm resiliency: n $>$ 3f
    \end{itemize}

\end{frame}

\section{Algorithm}
\begin{frame}
    \frametitle{Overview}
    \begin{itemize}
        \item State machine replication 
        \item R replicas denoted by {0,..,$|$R$|$-1} where R = 3f + 1
        \item Views: primary and backups
            \begin{itemize}
                \item p = v mod $|$R$|$; where v - view number, p - primary
                \item Primary failure triggers changes
            \end{itemize}
        \item Steps
            \begin{itemize}
                \pause
                \item Client sends a request to invoke a service operation to the primary
                    \pause
                \item Primary multicasts the request to the backups
                    \pause
                \item Replicas execute the request and reply to client
                    \pause
                \item Client waits for f + 1 replies from different replicas with the same result
            \end{itemize}
    \end{itemize}
\end{frame}
\begin{frame}
\frametitle{Client}
    \begin{itemize}
        \item $\langle$ REQUEST,o,t,c $\rangle$${_\sigma}_i$
        \item $\langle$ REPLY,v,t,c,i,r $\rangle$${_\sigma}_i$
        \item Client timeout
    \end{itemize}
\end{frame}
\begin{frame}
\frametitle{Normal-case}
    \begin{itemize}
        \item Replica state: \pause state of service, message log, view number
            \pause
        \item Three-phase protocol 
            \begin{itemize}
                \pause
                \item pre-prepare, prepare, commit
                \item pre-prepare and prepare: \pause totally order requests to a same view
                \item prepare and commit: \pause commits totally ordered across views
            \end{itemize}
    \end{itemize}
\end{frame} 
\begin{frame}
\frametitle{Pre-prepare}
    \begin{itemize}
        \item $\langle\langle$ PRE-PREPARE,v,n,d $\rangle$${_\sigma}_i$, m$\rangle$
        \item Backup accepts pre-prepare provided:
            \begin{itemize}
                \item signatures and digest are correct
                \item in view v
                \item no previous PP such that v'=v, n=n', d$\neq$d'
                \item h $<$ n $<H$
            \end{itemize}
    \end{itemize}
\end{frame}
\begin{frame}
\frametitle{Prepare}
    \begin{itemize}
        \item multicast $\langle$ PREPARE,v,n,d $\rangle$${_\sigma}_i$ and log
        \item prepared(m, v, n, i) true if i has logged:
            \begin{itemize}
                \item request m
                \item pre-prepare(m,v,n)
                \item 2f matching prepares from different backups
             \end{itemize}
        \item prepared(m', v, n, i) false if D(m')$\neq$D(m)  
    \end{itemize}
\end{frame}
\begin{frame}
\frametitle{Commit}
    \begin{itemize}
        \item $\langle$ COMMIT,v,n,D(m), i$\rangle$${_\sigma}_i$
        \item committed-local(m,v,n,i) true if:
            \begin{itemize}
                \item prepared(m,v,n,i) is true
                \item i has accepted 2f + 1 commits for m
            \end{itemize}
        \item committed(m,v,n)
             \begin{itemize}
                \item prepared(m,v,n,i) true for every i in f + 1 non-faulty replicas 
            \end{itemize}
       \end{itemize}
\end{frame}



\begin{frame}
\frametitle{Normal-Case Operation}
\begin{figure}
\includegraphics[width=60mm]{normalop.jpeg}
\caption{Normal-Case Operation}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Garbage Collection}
    \begin{itemize}
        \item Trimming the log
        \item Correctness of state: $\langle$ CHECKPOINT,n,d, i$\rangle$${_\sigma}_i$
        \item Water marks: H = h + k
    \end{itemize}
\end{frame}
\begin{frame}
\frametitle{View Changes}
    \begin{itemize}
        \item Ensures liveness
        \item View change
            \begin{itemize}
                \item multicast $\langle$ VIEW-CHANGE,v+1,n,C,P,i$\rangle$${_\sigma}_i$
            \end{itemize}
        \item New view
            \begin{itemize}
            \item multicast $\langle$ NEW-VIEW,v+1,V,O$\rangle$${_\sigma}_p$
            \end{itemize}
   \end{itemize}
\end{frame}
\begin{frame}
\frametitle{Non-Determinism}
    \begin{itemize}
        \item Primary proposed
        \item Replica driven
    \end{itemize}
\end{frame}

\section{Optimizations}
\begin{frame}
    \begin{itemize}
        \item MAC over signatures
        \item Digest replies 
        \item Tentative execution
        \item Read-only operations
    \end{itemize}
\end{frame} 

\section{BFT Library}  

\begin{frame} 
\begin{figure}
\includegraphics[width=60mm]{arch.jpeg}
\caption{Replicated File System Architecture}
\end{figure}
\end{frame}

\begin{frame} 
    \frametitle{Interface}
    {\textbf Client}\\
int Byz\_init\_client(char *conf)\\
int Byz\_invoke(Byz\_req *req, Byz\_rep *rep, bool ro)\\
{\textbf Server}\\
int Byz\_init\_replica(char *conf, char *mem, int size, proc exec,  proc nondet)\\
void Byz\_modify(char *mod, int size)\\
{\textbf Server upcalls}\\
int execute(Byz\_req *req, Byz\_rep *rep, Byz\_buffer *ndet, int cid, bool ro);\\
int nondet(Seqno seqno, Byz\_req *req, Byz\_buffer *ndet)\\
\end{frame}

\section{Benchmarks}  
\begin{frame} 
    \frametitle{Setup}

     \begin{itemize}
        \item Normal-case behavior
        \item One client and four replicas
        \item Micro-Benchmark
        \item Andrew Benchmark
    \end{itemize}
\end{frame}

\section{\$}
\begin{frame}
    \url{http://www.cs.utexas.edu/~adityaj/}
\end{frame}


\end{document}

